/*
题目: 最大加号标志
在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0

返回  grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。

https://leetcode.cn/problems/largest-plus-sign/description/
 */
public class OrderOfLargestPlusSign {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        // 动态规划
        // 记录 以某个点为准 向四个方向展开后的 最短连续 1
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i ++) {
            Arrays.fill(dp[i], n);
        }
        Set<Integer> banned = new HashSet<> ();
        for (int[] m : mines) {
            banned.add(m[0] * n + m[1]);
        }

        int src = 0;
        for (int i = 0; i < n; i ++) {
            int count = 0;
            /* left */
            for (int j = 0; j < n; j ++) {
                if (banned.contains(i * n + j)) { // 包含
                    count = 0;
                } else {
                    count ++; // 最长连续 1 ++
                }
                // 需要求解的是 四个方向上的 最短连续 1
                dp[i][j] = Math.min(dp[i][j], count);
            }

            count = 0;
            /* right */
            for (int j = n - 1; j >= 0; j --) {
                if (banned.contains(i * n + j)) {
                    count = 0;
                } else {
                    count ++;
                }
                dp[i][j] = Math.min(dp[i][j], count);
            }
        }

        // 需要先将 left 和 right 都记录下来, 再去更新 up 和 down, 否则数据没更新完导致后面数据错误
        for (int i = 0; i < n; i ++) {
            // 至此记录 上和下, 原 i 需要变成列
            /* up */
            int count = 0;
            for (int j = 0; j < n; j ++) {
                if (banned.contains(j * n + i)) {
                    count = 0;
                } else {
                    count ++;
                }
                dp[j][i] = Math.min(dp[j][i], count);
            }
            /* down */
            count = 0;
            for (int j = n - 1; j >= 0; j --) {
                if (banned.contains(j * n + i)) {
                    count = 0;
                } else {
                    count ++;
                }
                dp[j][i] = Math.min(dp[j][i], count);
                src = Math.max(dp[j][i], src);
            }
        }

        return src;
    }
}
